package leetcode.hot100;

import leetcode.common.TreeNode;

@SuppressWarnings("all")
public class _543_二叉树的直径 {

    /**
     * 两结点之间的路径长度是以它们之间边的数目表示
     *           1
     *          / \
     *         2   3
     *        / \
     *       4   5
     * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]
     */
    int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return res;
    }

    int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);   //当前结点左孩子深度
        int right = depth(root.right); //当前结点右孩子深度
        res = Math.max(left + right, res); //以当前结点为起点的直径
        return Math.max(left, right) + 1;  //当前结点的自己的深度
    }

    /**
     * res = Math.max(left + right, res);
     * 核心，巧妙的地方就是这一步，在递归的过程中会一直压栈到最后，当触发递归基条件后就开始弹栈
     * 在弹栈的过程中就可以自下而上的去更新当前结点的深度和以当前结点为中心的直径
     */
}
